斯坦福ICLR2019图网络最新论文：图神经网络的表征能力有多强？

导语

深度学习领域关于图神经网络(Graph Neural Networks，GNN)的研究热情日益高涨，图网络已经成为2019年各大深度学习顶会的研究热点。GNN 处理非结构化数据时的出色能力使其在网络数据分析、推荐系统、物理建模、自然语言处理和图上的组合优化问题方面都取得了新的突破。但是，大部分的图网络框架的建立都是基于研究者的先验或启发性知识，缺少清晰的理论支撑。

本文介绍ICLR2019的一篇论文，提出基于WL图同构测试的理论框架，为众多的GNN框架给出了精彩的理论分析，并提出了一个简单但是强大的图网络框架 GIN(Graph Isomorphism Networks)，并验证了GIN在图分类任务上的卓越性能。

在刚刚过去的ICLR 2019会议中，一篇 Oral 的会议文章回答了很多图网络研究者都在思考的一个问题：图神经网络到底有多厉害 ( How Powerful are Graph Neural Networks) ？

本文是斯坦福大学复杂网络数据分析大佬 Jure Leskovec 教授团队的最新力作(Node2Vec、GraphSAGE等经典工作也是出自该团队)。自该工作公开以来，已经有了近70的citations，表明图网络社区对该工作的关注度很高。

论文题目：

How Powerful are Graph Neural Networks?

论文地址：

https://arxiv.org/pdf/1810.00826.pdf

众所周知，图网络(GNNs)的新变体层出不穷，但是却鲜有对图网络框架的理论分析。Kipf在2017年提出的GCN中，曾从图上的谱分析的角度给出了GCN的理论基础；近期也有日本研究者从图信号处理的角度，表明GNNs只是一个低频滤波器(arxiv.org/abs/1905.09550)。而本文尝试从图同构的角度出发，以Weisfeiler-Lehman Isomorphism Test (WL test)为基础，给出了GNNs表征能力的精彩理论分析，具体的贡献总结如下：

1. 作者表明，在区别不同图结构时，GNNs最多只能取得和 WL test 一样效果，即，GNNs表征能力的上限是WL test；

2. 作者也给出了构建GNNs的条件，满足这些条件后，GNNs的表征能力和 WL test一样强；

3. 给出了GCN和GraphSAGE等传统图网络框架不能区分的网络结构；

4. 建立了一个简单的框架GIN，并在理论上证明了其表征能力和 WL test一样强。

总结起来，全文需要回答两个关键性的问题：

1. GNNs表征能力的上限是什么？

2. 怎样的GNNs 框架设计才能达到最好的表征能力？

这里的表征能力是指对图拓扑结构的表征是否能有效区分不同的图结构。所以，是否能够判断图同构便成了GNNs表征能力的判断标准。如果GNNs对图的表征能区分同构或不同构的图，则表明其有较强的表征能力。

但图同构是一个非常难的问题，至今还没有有效的方法判断两个图是否同构，所幸WL test是一个非常有效的图同构检验近似方法，对图结构具有很强的表征能力。那么，GNNs能否具有WL test一样的表征能力？有的话，怎么设计框架怎样达到和WL一样的水平？

背景知识

GNNs

大多数的GNNs可以归结为 aggregation based 或者 message-passing based 的框架，主要包含聚合邻居信息和更新节点信息两步，AGGREGATE 和 COMBINE：

不同的GNNs区别就在与采用不同的 AGGREGATE 和 COMBINE 函数。比如GCN的 AGGREGATE 函数就是采用的mean-pooling，而GraphSAGE则是采用max-pooling。

The Weisfeiler-Lehman Isomorphism Test

WL test是一种有效的检验两个图是否同构的近似方法。当我们要判断 Graph1 和 Graph2 是否同构时，WL test 的主要步骤如下图所示，通过聚合节点邻居的 label，然后通过 hash 函数得到节点新的 label，不断重复知道每个节点的 label 稳定不变。   

稳定后，统计两张图的label的分布，如果分布相同，则一般认为两张图时同构的。

我们可以发现，WL test 方法的步骤和GNNs具有异曲同工之妙，都是通过不断聚合邻居信息，得到节点的新表示，这也是为什么Kipf在2017年GCN的论文中单独讨论和GCN和WL test关系的原因。而正是这种统一性，才使得本文能以 WL test 为基础来分析GNNs框架。

主要的理论结果

本文作者基于WL test和GNNs框架的相似性，层层推进，给出了一系列重要的结果。

首先，作者说明GNNs框架的表征能力不会超过WL test：

对于两个不同构的图，如果GNNs能将其map到不同embs，那么WL test也会得出不同构的结论。既然GNNs不能超过WL test， 那么如何才能和WL test一样有效呢？

上图展现了WL test与GNNs在表征网络结构时的共同点：一个节点的表征都是由以该节点为父节点的子树信息聚合得到(中间图)。而在聚合的过程中，WL test最大的特点是其聚合函数采用的是单射(injective)的 hash 函数。那么，是否将 GNNs 的的聚合函数也改成单射(injective)函数 就能达到和WL test一样的效果呢？作者给出了肯定的答案：

该结论说明：如果GNNs的聚合函数是定义在multiset上的单射函数，那么GNNs和WL的表征能力一样。也给出了设计 powerful 的 GNNs 框架的首要条件：injective。

但是，上述结论虽然给出了设计有效GNNs框架的充分条件，但是并没有给出具体的设计指南，我们仍然不知道如何才能找到具有单射性质的聚合函数。而如下的结论很好的给出了答案：

上述结论表明，如果我们把节点上一层的表征表示为c，其邻居的表征的集合表示为X，那么任意关于 c 与 X 的函数 g (当然包括单射函数) 都可以表示为\phi 与 f 的复合形式。而该复合函数可以用万能拟合函数MLPs来拟合，至此，作者们就得到了一个非常简单的GNNs框架：

称之为GIN (Graph Isomorphism Networks)， 该框架最大的特点就是简单，并且其有效性具有理论保证。在图分类的实验中，该框架也表现出了SOTA的性能。

对于传统GNNs的分析

很过经典的GNNs框架采用 mean-pooling 或者 max-pooling的方法，而作者提出，这些聚合方法并不是单射函数，其不能区分一些不同的局部结构，从而导致框架的表征能力下降：

比如上图所示：相同的颜色代表相同的节点属性。在图a, b, c中，节点 v 与 v‘ 的局部结构均不相同，但是Mean 和 Max 却不能有效区分，会导致两种局部结构得到相同的节点表征，从而丢失了网络的结构信息。

但是采用Mean和Max-poling的框架(GCN，GraphSAGE)表现都很好，那么他们学到了什么呢？

作者认为：

Mean-pooling 致力于学习节点 feature 的分布： 所以，在下述情况中，Mean也能表现的很好：

1. 当我们的任务之和节点feature的分布有关，而与具体的局部结构无关时

2. 当节点的具有丰富的feature，很少重复时

这就解释了为什么GCN在做节点分类时，为什么会有那么好的效果：因为每个节点的特征很难会重复。

Max 学的是 underlying set：Max处理Multiset时，只关心其对应的underlying set。所以，Max既没有学到局部结构，也没有学到分布。当我们关心Representative element或者“skeleton”时，Max会有好效果。

实验

本文为了体现GIN在表征网络结构信息的的出色能力，选择用网络分类实验来验证其有效性。

Training Set Accuracy

我们需要强调的一点时，文中对GNNs表征能力的分析只关系其拟合能力，即是否能对训练数据进行充分的拟合，这一点可以由训练过程的 training set accuracy 来验证：

上图表明，在5个数据集上，GIN的训练精度都是最高，说明其拟合能力最好，即其对网络结构的表征能力最强。值得注意的是，GIN的训练精度最高也没有超过WL subtree kernel的精度，这样验证了文中的理论结果：GIN和 WL 一样强，但是不会超过WL。

Test Set Accuracy

在网络分类实验的测试集上，GIN在多个数据集上均取得了SOTA的成绩，表明GIN框架不仅有最强的拟合能力，还具有优秀的泛化能力。

小结

该论文对基于聚合的GNN做了非常精彩的理论分析，给出了GNNs的表征能力的上界，同时给出了如何设计GNNs才能使其表征能力最强的条件。在此基础上，设计了一个异常简单的图网络框架GIN，但是却非常的有效，在图分类任务上取得了SOTA的成绩。这篇工作表明了基于理论分析的框架构建是多么的有效，使我们必须承认，对更加广义的GNNs的理论分析是图网络社区的基础性任务。

其他链接

CLR 2019 OpenReview (推荐阅读):

https://openreview.net/forum?id=ryGs6iA5Km

论文的Github页面:

https://github.com/weihua916/powerful-gnns

相关博客：

https://asail.gitbook.io/hogwarts/graph/how_powerful

https://www.davidbieber.com/post/2019-05-10-weisfeiler-lehman-isomorphism-test/

课程推荐

录播地址：

http://campus.swarma.org/play/coursedetail?id=10936

作者：高飞

编辑：张爽

---

集智俱乐部QQ群｜877391004

商务合作及投稿转载｜[e-mail]

◆ ◆ ◆

搜索公众号：集智俱乐部

加入“没有围墙的研究所”

让苹果砸得更猛烈些吧！